#
# @lc app=leetcode.cn id=50 lang=python3
#
# [50] Pow(x, n)
#

# @lc code=start


class Solution:
    # 分治
    # 1. 出口
    # 2. 处理当前层（分为子问题）
    # 3. 调用下一层（处理子问题）
    # 4. 合并结果
    # 5. 重置状态
    """
    2^10： (2^5)^2  2^5: (2^2)*2
    pow(x, n):
        subproblem: pow(x, n//2)
    O (logN)

    merge:
    if n % 2 != 0:
        # 奇数
        res = subres * subres * x
    else:
        # 偶数
        res = subres * subres
    """

    def fastPow(self, x, n):
        if n == 0:
            return 1.0

        half = self.fastPow(x, n // 2)
        if n % 2 == 0:
            return half * half
        else:
            return half * half * x

    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1 / x
            n = -n

        return self.fastPow(x, n)

    # @lc code=end
